package sf.sort;

import java.util.LinkedList;

public class BucketSort implements Sort{
    // 桶排序，本质就是通过多个桶来存数据
    @Override
    public void sort(int[] unsorted) {
        // 本质就是插入排序，只是分成了部分数据
        int[][] buckets = new int[10][unsorted.length];// 分成10个桶
        int[] indexes = new int[10];
        // 算下总长度
        int maxLength = Integer.MIN_VALUE;
        for (int i : unsorted) {
            maxLength = Math.max(maxLength, String.valueOf(i).length());
        }
        for (int value : unsorted) {
            final String s = String.valueOf(value);
            int length = s.length();
            int c = 0;
            if (length >= maxLength) {
                c = s.charAt(0) - '0';
            }
            insert(buckets[c], indexes[c]++, value);
        }
        int k = 0;
        for (int i = 0; i < buckets.length; i++) {
            int[] bucket = buckets[i];
            for (int j = 0; j < indexes[i]; j++) {
                unsorted[k ++] = bucket[j];
            }
        }
    }

    public void insert(int[] arr, int k, int num) {
        int i = k;
        for (; i > 0 && arr[k-1] > num; i--) {
            arr[i] = arr[i-1];
        }
        arr[i] = num;
    }

}
